package com.yitiao.data_algorithms.leetcode.editor.cn;
import com.yitiao.data_algorithms.leetcode.editor.cn.base.ListNode;
import com.yitiao.data_algorithms.leetcode.editor.cn.base.TreeNode;

import java.util.HashSet;
import java.util.Set;

class ContinuousSubarraySum{
    // 2022-08-25 12:45:35
    public static void main(String[] args) {
        Solution solution = new ContinuousSubarraySum().new Solution();
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        // 连续子数组和 = 前缀和的差
        // 先构建前缀和
        int[] sum = new int[nums.length + 1];
        for (int i = 1; i < sum.length; i++) {
            sum[i] = sum[i-1] + nums[i-1];
        }

        // 同余定理：如果两个数相减能被 k 整除，则连个数 % k 的余数相同。
        Set<Integer> set = new HashSet<>();
        for (int i = 2; i < sum.length ; i++) {
            set.add(sum[i-2] % k);
            if (set.contains(sum[i] % k)){
                return true;
            }

        }
        return false;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}